# -*- coding: utf-8 -*-

''' Autor: Neuza Figueira - n.º 6036 '''

from random import randint
from time import clock
import matplotlib.pyplot as plt


class CountingSort():
        ''' Class to handle Counting sort implementation and testing.'''

        def counting_sort(self, A, k):
                '''Python Implementation of Counting sort.'''
                '''@param A -> List to sort.'''
                '''@param k -> maximum value from list A.'''
                counter = [0] * ( k + 1 )
                
                for i in A:
                        counter[i] += 1
         
                total = 0;
                for i in range(len(counter)):
                        while 0 < counter[i]:
                                A[total] = i
                                total += 1
                                counter[i] -= 1

                return A


        def testCountingSort(self):
                '''Testing the complexity of Counting sort.'''
                Z = range(50, 1050, 50)
                T = []
                M = 400
                for n in Z:
                    A = [ randint(0, 100) for k in xrange(n)]
                    tempos = []
                    for k in range(M):
                        t1 = clock()
                        self.counting_sort(A, max(A))
                        t2 = clock()
                        tempos.append(t2-t1)
                    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
                    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
                    
                    T.append((n,media, var))

                X = [n for n, media, var in T]
                Y = [media for n, media, var in T]
                ct = 20e5
                Z = [n / ct for n, media, var in T]


                plt.grid(True)
                plt.ylabel(u'T(n) - tempo de execução médio em segundos')
                plt.xlabel(u'n - número de elementos')
                plt.plot(X,Y,'rs', label="resultado experimental")
                plt.plot(X, Z, 'b^', label=u"previsão teórica")
                plt.legend()
                plt.show()
                pass
